Protocols for sharing a wireless medium effectively among multiple users are generally denoted multiple access protocols, channel access schemes or medium access schemes. Multiple access protocols may as described in [1] be divided in two main categories: conflict-free protocols and contention-based protocols.
Conflict-free protocols are protocols ensuring that a transmission, whenever made, is successful, i.e. not interfered by other transmissions. Conflict-free transmission can be achieved by allocating the channel to the users either statically or dynamically. This is often denoted fixed and dynamic scheduling respectively. The benefit of precise coordination among stations is that it is believed to provide high efficiency, but comes at the expense of complexity and exchange of sometime large quantities of control traffic.
Contention-based protocols differ in principle from conflict-free protocols in that transmissions are not guaranteed to be successful. The protocol should therefore prescribe a procedure to resolve conflicts once they occur so that all message are eventually transmitted successfully.
Multiple access protocols can also be divided based on the scenario or application for which they have been designed. Some protocols are suitable for access towards/from a single station, e.g. a base station in a cellular system, whereas other protocols are designed to operate in a distributed environment. An important distinction for the distributed case is whether the protocol is designed primarily for a single hop case, i.e. communication only with a designated neighbor within reach, or if it is particularly designed for a multi-hop scenario.
In a multi-hop scenario, information may be transmitted over multiple hops between source and destination instead of directly in a single hop. In general, the multi-hop approach offers several advantages such as lower power consumption and higher information throughput compared to a direct one-hop approach. In a multi-hop network, nodes out of reach from each other can benefit from intermediately located nodes that can forward their messages from the source towards the destination. Multi-hop networks can be so-called ad hoc networks where nodes are mostly mobile and no central coordinating infrastructure exists, but the idea of multi-hop networking can also be applied when nodes are fixed.
In prior art routing techniques based on an underlying shortest-path routing protocol (such as Bellman-Ford based routing), a well-defined multi-hop route from source to destination is determined based on routing cost information passed through the system. Simplified, each node or station knows the costs of its outgoing links, and broadcasts this information to each of the neighboring nodes. Such link-cost information is typically maintained in a local database in each node and based on the information in the database, a routing table is calculated using a suitable routing algorithm. In general, shortest path and similar routing techniques lead to the existence of a single route for each source-destination pair. A very simple shortest-path based routing scheme, though not the most efficient, may for example use the well known ALOHA contention-based multiple access protocol.
There are existing protocols (which may use an underlying shortest-path protocol) based on the concept of exploiting multiple nodes in the forwarding process with a more or less active routing choice. For example, the protocol called EIGRP (Enhanced
Interior Gateway Routing Protocol) [2] is a routing protocol, used mainly in a fixed network that allows random-based forwarding to one out of several routers. Random-but-forward routing [3] by Sylvester and Kleinrock is similar to EIGRP, i.e. random-based forwarding of packets to one out of several packet radio network routers, but it also includes an important amendment; it is ensured that a packet is always heading in the general correct direction. Alternate path routing [4] by DARPA (Defense Advance Research Project Agency) allows a packet that is retransmitted over a link to be duplicated while multicasted to several nodes from which the packet again follows a shortest path routing approach. Primary N/M-forwarding [5] is based on the idea that a node tries to send a packet at most N times to a node and then, if failing, it tries the next node up to N times. This procedure is repeated for at most M nodes prior to dropping the packet. The advantage of alternate path routing and primary N/M-forwarding is that they can adapt to the local communication situation, including congestion and temporarily poor communication due to e.g. fading or interference fluctuations.
Changes or fluctuations within the system over time can create windows or peaks of opportunity that enable signal transmissions to be more successful than at other times and conditions. Plain shortest-path techniques and associated prior art routing techniques do not have the ability to recognize these windows of opportunity, since there is no relative information stored by each node or station. In contrast, opportune routing [6, 7] exploit to some extent the opportunities that system changes and fluctuations provide. In the context of wireless routing in particular, overall system performance is degraded when link quality varies rapidly over time (e.g. due to Rayleigh fading). However, opportune routing partly mitigates this performance degradation by making use of the windows of opportunity that these fluctuations provide. With opportune routing, there is not a single route for each source-destination pair, i.e. similar to EIGRP, random-but-forward and to some extent also alternate path routing and primary N/M-forwarding. Instead, data packets follow a route that is somewhat random, while still leading from source to destination. Consequently, when a shortest-path procedure is used, consecutive packets will generally be sent over the same route, whereas when opportune routing is used, consecutive packets may be routed over different paths but in the same direction.
However, die general monitoring in [6, 7] is a slow process. Monitoring is either handled by listening on bypassing messages or by occasionally sending out so-called probes. When a probe is sent out, a response that includes information on for example path loss is expected back. When there is a delay between the probe and data transmission, then the returned input information for the forwarding algorithm may become obsolete by the time the data is transmitted. A particularly undesirable consequence is that existing opportune routing, and also plain shortest-path based routing techniques, do not handle possible diversity effects efficiently.
Selection diversity forwarding (SDF) [8] is a technique for efficiently handling diversity effects in a near optimal manner. This novel approach is based on directing transmission from an originating station to a group of receivers or relay nodes nearby. When one or more of the receiving nodes have replied, one of the replying nodes is selected and a command message is transmitted to the selected relay node instructing it to assume responsibility for forwarding the data message. The process is repeated for all subsequent responsible nodes until the information reaches the destination. By following this approach, both branch diversity and capture effects can be exploited in the data forwarding process. In particular, branch diversity reduces the need to use interleaved data together with coding to combat fading channels, which in turn means smaller delay and consequently higher throughput. The capture effect refers to a phenomenon in which only the stronger of two signals that are at or near the same frequency is demodulated, while the weaker signal is suppressed and rejected as noise. In conjunction with multiple receiving stations, the capture effect provides a high degree of robustness when data transmissions collide. SDF utilizes a slow underlying cost protocol, but allows instantaneous adaptation to fast channel fluctuations per se.
Similar ideas for exploiting fluctuations, but for normal cellular networks with single hops, can be found in [9, 10 and 11], which refer to High Speed Downlink Packet Access (HSDPA), High Data Rate (HDR) and Opportunistic Beamforming (OB), respectively. HSDPA and HDR are very similar to each other. Opportunistic Beamforming however is different from a functional point of view in that OB randomly points, or continuously sweeps an antenna beam, in different directions, whereas HSDPA and HDR has no notion of beamforming. In particular, Opportunistic Beamforming [11] exploits the opportunistic idea and then utilizes the opportunistic approach with respect to beamforming to enhance system capacity in a cellular system or at a base station. However, the concept of HSDPA, HDR and OB as such does not relate to multi-hopping. OB is essentially an extension of fast scheduling at the base station taking fast channel fluctuations into account, which has been suggested both for CDMA 2000 HDR and WCDMA HSDPA.